package com.captain.sort;

import java.util.Arrays;

/**
 * Des: 插入排序
 *
 * @author XL
 * @Date 2021/7/23 8:59
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = new int[]{6, 20, 4, 4, 3, 1, 3, 2, 1};
        int[] sort = insertionSort(arr);
        System.out.println(Arrays.toString(sort));
    }

    /**
     * 插入排序
     * 插入排序 ,把整个数组分为两部分 , 已经排序和未排序
     * 从未排序的中抽出数插入到已经排序中
     *
     * @param arr
     * @return
     */
    public static int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int r = arr[i];
            int k = i;
            for (; k > 0; k--) {
                //退出条件
                if (r > arr[k - 1]) {
                    break;
                }
                //交换位置
                arr[k] = arr[k - 1];
            }
            arr[k] = r;
        }
        return arr;
    }
}
